﻿#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

// show debug log
static bool isDebug = true;


// 打印数组
void printArray(vector<int> ary, int start, int end) {
	const int len = end - start + 1;
	if (len == 0) {
		printf("[]\n");
		return;
	}
	// 字符串
	for (int i = start; i <= end; i++)
	{
		// 用数组‘,’形式分隔元素
		printf(i == start ? "[" : ",");
		printf("%d", ary[i]);
	}
	printf("]\n");
}
void printArray(int *ary, int start, int end) {
	const int len = end - start + 1;
	if (len == 0) {
		printf("[]\n");
		return;
	}
	// 字符串
	for (int i = start; i <= end; i++)
	{
		// 用数组‘,’形式分隔元素
		printf(i == start ? "[" : ",");
		printf("%d", ary[i]);
	}
	printf("]\n");
}
void printArray(int *ary, int len) {
	if (len == 0) {
		printf("[]\n");
		return;
	}
	// 字符串
	for (int i = 0; i < len; i++)
	{
		// 用数组‘,’形式分隔元素
		printf(i == 0 ? "[" : ",");
		printf("%d", ary[i]);
	}
	printf("]\n");
}

///////////////////////////////////////////////////////// 递归排序法
// 排序合并
void Merge(vector<int>& Array, int front, int mid, int end) {
	vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
	vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
	
	int idxLeft = 0, idxRight = 0;
	LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
	RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
	if (isDebug) {
		printf("左右数组末尾插入最大int整数。\n");
		printf("左数组：");
		printArray(Array, front, mid);
		printf("右数组：");
		printArray(Array, mid, end);
	}
	// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
	for (int i = front; i <= end; i++) {
		if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
			Array[i] = LeftSubArray[idxLeft];
			idxLeft++;
		}
		else {
			Array[i] = RightSubArray[idxRight];
			idxRight++;
		}
	}
	if (isDebug) {
		printf("遍历数组%d至%d，合并数组。\n", front, end);
		printArray(Array, front, end);
	}
}

/// 递归：自顶向下
void MergeSort(vector<int>& Array, int front, int end) {
	if (front >= end)
		return;
	const int mid = front + (end - front)/2;
	if (isDebug) {
		printf("\n数组长度%d，起始位置%d，终止位置%d，中位数%d\n", end - front, front, end, mid);
	}
	MergeSort(Array, front, mid);
	MergeSort(Array, mid + 1, end);
	Merge(Array, front, mid, end);
}


/////////////////////////////////////////////////////////////////////// 迭代法 自下而上
template<typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能
void merge_sort(T arr[], int len) {
	T* a = arr;
	// new一个新的等长空间，用于辅助排序
	T* b = new T[len];
	// 循环步长成倍增长
	for (int seg = 1; seg < len; seg += seg) {
		// 元素分组
		for (int start = 0; start < len; start += seg + seg) {
			// 组内划分数组
			int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
			if (isDebug) {
				printf("\n数组长度%d，起始位置%d，终止位置%d，中位数%d\n", high - low, low, high, mid);
			}
			int k = low;
			int start1 = low, end1 = mid;
			int start2 = mid, end2 = high;
			if (isDebug) {
				printf("左数组：");
				printArray(arr, start1, end1 - 1);
				printf("右数组：");
				printArray(arr, start2, end2 - 1);
			}
			// 合并排序数组至b
			while (start1 < end1 && start2 < end2)
				b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
			// 合并左侧剩余的至b
			while (start1 < end1)
				b[k++] = a[start1++];
			// 合并右侧剩余的至b
			while (start2 < end2)
				b[k++] = a[start2++];
			if (isDebug) {
				printf("排序后数组：\n");
				printArray(arr, low, high - 1);
			}
		}
		// 交换ab指针
		T* temp = a;
		a = b;
		b = temp;
	}
	// 确保数据拷贝到arr数组
	if (a != arr) {
		for (int i = 0; i < len; i++)
			b[i] = a[i];
		b = a;
	}
	// 释放临时内存b
	delete[] b;
}

int main() {
	//vector<int> arr = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
	//const int len = arr.size();
	//if (isDebug) {
	//	printf("数组长度%d，排序前数组：\n", len);
	//	printArray(arr, 0, len-1);
	//}
	//MergeSort(arr, 0, len-1);

	int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
	const int len = (int)sizeof(arr) / sizeof(*arr);
	if (isDebug) {
		printf("数组长度%d，排序前数组：\n", len);
		printArray(arr, len);
	}
	merge_sort(arr, len);
	if (isDebug) {
		printf("数组长度%d，排序后数组：\n", len);
		printArray(arr, len);
	}
	return 0;
}